Brainman(POJ 1804)

样例输入:
4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

样例输出:
Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

//归并排序计算逆序数
#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN=1000+10;

int arr[MAXN];
int temp[MAXN];
int number;

void Combine(int left,int middle,int right)
{
    int i=left;
    int j=middle+1;
    int k=left;
    while(i<=middle&&j<=right)
    {
        if(arr[i]<=arr[j]){
            temp[k++]=arr[i++];
        }else{
            number+=middle+1-i;//与归并排序相比,仅多加一行
            temp[k++]=arr[j++];
        }
    }
    while(i<=middle)
        temp[k++]=arr[i++];
    while(j<=right)
        temp[k++]=arr[j++];
    for(k=left;k<=right;k++)
    {
        arr[k]=temp[k];
    }
}

void MergeSort(int left,int right)
{
    if(left<right){
        //int middle=(left+right)/2;防止数据超过int界限
        int middle=left+(right-left)/2;
        MergeSort(left,middle);
        MergeSort(middle+1,right);
        Combine(left,middle,right);
    }
}

int main()
{
    int caseNumber;
    scanf("%d",&caseNumber);
    for(int caseOrder=1;caseOrder<=caseNumber;++caseOrder){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        number=0;
        MergeSort(0,n-1);
        printf("Scenario #:%d\n",caseOrder);
        printf("%d\n\n",number);
    }
    return 0;
}
